Step 2: push(k) & bubble_up(i)

How do we add a new element k?
  1. Insert: Put k at the *end* of the array.
  2. Fix: The heap property might be broken. We "bubble up" the new element.

Guidance for Step 2

  • push(): Your blank is the starting index for bubble_up. Where did you just add the new element? (Hint: len(self.heap) - 1)
  • bubble_up(): Fill in the parent index formula you defined in the docstring.
  • Recursive Call: After you swap, the element is now at the parent index. You must continue bubbling up from that new position. 
# ... (inside PriorityQueue class) ...

    def push(self, k):
        """Adds a new key 'k' to the priority queue."""
        # 1. Add the new element to the end of the list
        self.heap.append(k)
        
        # 2. Start the recursive bubble up from the last element's index
        self.bubble_up(________)

    def bubble_up(self, i):
        """
        Recursively moves the element at index 'i' up the heap to
        restore the max-heap property.
        """
        # Base Case 1: We are at the root (index 0).
        if i == 0:
            return

        # Get the parent index
        parent = ________
        
        # Base Case 2: The parent is larger, so the heap property is met.
        if self.heap[parent] >= self.heap[i]:
            return

        # Recursive Step: Swap with parent and continue bubbling up.
        self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
        self.bubble_up(________)
Copied!